package second.codeTop.package1;

import java.util.HashMap;
import java.util.Stack;

/**
 * @ClassName LC20
 * @description: 有效的括号
 * @author: 荣燊
 * @create: 2022-03-03 10:26
 **/
public class LC20 {
    public static void main(String[] args) {
        String s = "(])";
        System.out.println(isValid(s));
    }

    // 常规写法1
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0));
        for (int i=1; i<s.length(); i++) {
            if (stack.isEmpty()) {
                stack.push(s.charAt(i));
            } else {
                if (s.charAt(i) == '(') {
                    stack.push('(');
                }
                if (s.charAt(i) == '{') {
                    stack.push('{');
                }
                if (s.charAt(i) == '[') {
                    stack.push('[');
                }
                if (s.charAt(i) == '}') {
                    if ('{' == stack.peek()) {
                        stack.pop();
                    } else {
                        stack.push(s.charAt(i));
                    }
                }
                if (s.charAt(i) == ']') {
                    if ('[' == stack.peek()) {
                        stack.pop();
                    } else {
                        stack.push(s.charAt(i));
                    }
                }
                if (s.charAt(i) == ')') {
                    if ('(' == stack.peek()) {
                        stack.pop();
                    } else {
                        stack.push(s.charAt(i));
                    }
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }

    static HashMap<Character, Character> map = new HashMap<>();
    // 优化
    public static boolean isValid1(String s) {
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        Stack<Character> stack = new Stack<>();
        if (s.length() % 2 == 1) {
            return false;
        }
        stack.push(s.charAt(0));
        for (int i=1; i<s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                if (!stack.isEmpty() && map.get(s.charAt(i)) == stack.peek()) {
                    stack.pop();
                } else {
                    stack.push(s.charAt(i));
                }
            } else {
                stack.push(s.charAt(i));
            }
        }
        return stack.isEmpty();
    }
}
